/**
 * //给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
 * //
 * // 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
 * //
 * //
 * //
 * // 示例 1：
 * //
 * //
 * //输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word =
 * //"ABCCED"
 * //输出：true
 * //
 * //
 * // 示例 2：
 * //
 * //
 * //输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word =
 * //"SEE"
 * //输出：true
 * //
 * //
 * // 示例 3：
 * //
 * //
 * //输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word =
 * //"ABCB"
 * //输出：false
 * //
 * //
 * //
 * //
 * // 提示：
 * //
 * //
 * // m == board.length
 * // n = board[i].length
 * // 1 <= m, n <= 6
 * // 1 <= word.length <= 15
 * // board 和 word 仅由大小写英文字母组成
 * //
 * //
 * //
 * //
 * // 进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？
 * // Related Topics 数组 回溯 矩阵 👍 1364 👎 0
 */

package com.xixi.basicAlgroithms.BreadthWidthFirstSearch;

public class ID00079WordSearch {
    public static void main(String[] args) {

        Solution solution = new ID00079WordSearch().new Solution();
        System.out.println(solution.exist(new char[][]{{'A', 'B', 'C', 'E'}, {'S', 'F', 'E', 'S'}, {'A', 'D', 'E', 'E'}}, "ABCESEEEFS"));
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        boolean[][] visited = null;
        boolean founded = false;

        public boolean exist(char[][] board, String word) {

            int m = board.length;
            int n = board[0].length;
            char[] wordChars = word.toCharArray();
            //防止二次使用字母，只需要记录本次启动后是否访问;

            visited = new boolean[m][n];
            //每个字母遍历一次
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {

                    dfs(board, wordChars, new int[]{i, j}, m, n, wordChars.length, 0);
                    if (founded) return founded;
                }
            }
            return founded;

        }

        public void dfs(char[][] board, char[] wordChars, int[] startPoint, int m, int n, int wordLengh, int nowIndex) {
            int x = startPoint[0];
            int y = startPoint[1];
            if (founded || visited[x][y] || nowIndex == wordLengh || wordChars[nowIndex] != board[x][y]) { //被访问过或者找到了，就break;
                return;
            }

            if (nowIndex == wordLengh - 1 && wordChars[nowIndex] == board[x][y]) { //最后一个字母都match
                founded = true;
                return;
            }

            //标记本次递归已经访问过了
            visited[x][y] = true;

            //上下左右找一遍
            int[][] differ = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
            for (int[] diff : differ) {
                int nextX = x + diff[0];
                int nextY = y + diff[1];
                if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && !visited[nextX][nextY]) { //未越界且未二次利用，其实也是终止条件
                    dfs(board, wordChars, new int[]{nextX, nextY}, m, n, wordLengh, nowIndex + 1);
                    if (founded) return; //剪枝
                }
            }

            visited[x][y] = false;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)


}